P3119 Grass Cownoisseur

我们应该用$Tarjan$缩点，将原图变为$GAD$图，同时记录每个强连通分量的节点个数，记为$num[i]$。

因为起点终点都是1，所以路径一定是一个环。我们可以处理出1到所有点的距离，存在$dis1$中（跑正图）和所有点到1的距离存在$dis2$中（跑反图）。注意，如果走不到就设为极小值。最短路跑的是点权，其实和边权差不多。

题目说可以逆向走一条有向边，我们设该边起点为$u$，终点为$v$，那么，答案就应为$num[belong[1]]+max(dis1[v]+dis2[u])$。

#include <cstdio>
#include <queue>
#include <stack>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 100000;
int n,m,x,y;
vector< int > Graph[ MAXN + 5 ];
stack< int > s;

int dfn[ MAXN + 5 ] , low[ MAXN + 5 ] , depth , cnt;
int belong[ MAXN + 5 ] , num[ MAXN + 5 ];
bool is[ MAXN + 5 ];

void Tarjan( int u ) {
    dfn[ u ] = low[ u ] = ++ depth;
    is[ u ] = 1 , s.push( u );
    
    int v;
    for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
        v = Graph[ u ][ i ];
        if( !dfn[ v ] ) {
            Tarjan( v );
            low[ u ] = min( low[ u ] , low[ v ] );
        }
        else if( is[ v ] )
            low[ u ] = min( low[ u ] , dfn[ v ] );
    }
    if( dfn[ u ] == low[ u ] ) {
        cnt ++;
        do{
            v = s.top();
            is[ v ] = 0 , s.pop();
            belong[ v ] = cnt;
            num[ cnt ] ++;
        }while( u != v );
    }
}

struct node{
    int v,w;
    node(){}
    node( int V , int W ) {
        v = V;
        w = W;
    }
    bool operator < ( const node &x ) const {
        return w < x.w;
    }
};
vector< int > lit_Graph1[ MAXN + 5 ];
vector< int > lit_Graph2[ MAXN + 5 ]; 
int dis1[ MAXN + 5 ],dis2[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void Spfa1( int s ) {
    queue< int > Q;
    while( !Q.empty() ) Q.pop();
    for( int i = 1 ; i <= n ; i ++ ) dis1[ i ] = -0x3f3f3f3f;
    memset( vis , 0 , sizeof( vis ) );
    dis1[ s ] = 0 , vis[ s ] = 1;
    
    Q.push( s );
    while ( !Q.empty() ) {
        int u = Q.front();
        Q.pop() , vis[ u ] = 0;

        for ( int i = 0 ; i < lit_Graph1[ u ].size() ; i ++ ) {
            int v = lit_Graph1[ u ][ i ];
            if ( dis1[ v ] < dis1[ u ] + num[ v ] ) {
                dis1[ v ] = dis1[ u ] + num[ v ];
                if ( !vis[ v ] ) {
                    vis[ v ] = 1;
                    Q.push( v );
                }
            }
        }
    }
}

void Spfa2( int s ) {
    queue< int > Q;
    while( !Q.empty() ) Q.pop();
    for( int i = 1 ; i <= n ; i ++ ) dis2[ i ] = -0x3f3f3f3f;
    memset( vis , 0 , sizeof( vis ) );
    dis2[ s ] = 0 , vis[ s ] = 1;
    
    Q.push( s );
    while ( !Q.empty() ) {
        int u = Q.front();
        Q.pop() , vis[ u ] = 0;

        for ( int i = 0 ; i < lit_Graph2[ u ].size() ; i ++ ) {
            int v = lit_Graph2[ u ][ i ];
            if ( dis2[ v ] < dis2[ u ] + num[ v ] ) {
                dis2[ v ] = dis2[ u ] + num[ v ];
                if ( !vis[ v ] ) {
                    vis[ v ] = 1;
                    Q.push( v );
                }
            }
        }
    }
}


int main( ) {
    scanf("%d %d",&n,&m);
    for( int i = 1 ; i <= m ; i ++ ) {
        scanf("%d %d",&x,&y);
        Graph[ x ].push_back( y );
    }
    for( int i = 1 ; i <= n ; i ++ )
        if( !dfn[ i ] ) Tarjan( i );
    for( int i = 1 ; i <= n ; i ++ )
    {
        for( int j = 0 ; j < Graph[ i ].size( ) ; j ++ ) {
            int u = belong[ i ] , v = belong[ Graph[ i ][ j ] ];
            if( u != v ) {
                lit_Graph1[ u ].push_back( v );
                lit_Graph2[ v ].push_back( u );
            }
        }
    }
    
    
    Spfa1( belong[ 1 ] );
    Spfa2( belong[ 1 ] );
    
    int Ans = num[ belong[ 1 ] ];
    for( int i = 1 ; i <= cnt ; i ++ ) {
        for( int j = 0 ; j < lit_Graph1[ i ].size( ) ; j ++ ) {
            int u = i , v = lit_Graph1[ i ][ j ];
            Ans = max( Ans , dis1[ v ] + dis2[ u ] + num[ belong[ 1 ] ] );
        }
    }
    printf("%d\n",Ans);
    return 0;
}